import java.util.Stack;

public class LeetCode20 {
    public boolean isValid(String s) {
        /*
         遇到左括号, 把要配对的右括号放入栈顶
         遇到右括号, 若此时栈为空, 返回 false，否则把它与栈顶元素对比
         */
        Stack<Character> stack = new Stack<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else {
                //* 若相等, 栈顶元素弹出, 继续对比下一组
                if (!stack.isEmpty() && stack.peek() == c) {
                    //若不等, 无效括号直接返回 false
                    stack.pop();
                } else {
                    return false;
                }

            }
        }

        /*
        若栈为空, 表示所有括号都配上对, 返回 true
        若栈不为空, 表示右没配对的括号, 应返回 false
         */
        return stack.isEmpty();
    }
}
